# 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
#  实现 LRUCache 类：
#  LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
#  int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
#  void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组
# key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
#  函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
#
#  示例：
# 输入
# ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
# [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
# 输出
# [null, null, null, 1, null, -1, null, -1, 3, 4]
import sys
from collections import OrderedDict


class Node:
    def __init__(self, key: int, value: int, next=None, pre=None):
        self.key = key
        self.value = value
        self.next = next
        self.pre = pre


class LRUCache:  # 自己实现LinkedHashMap(OrderedDict)
    def __init__(self, capacity: int):
        self.capacity, self.cachedMap = capacity, {}
        self.head, self.tail = Node(-sys.maxsize, -sys.maxsize), Node(-sys.maxsize, -sys.maxsize)
        self.head.next, self.tail.pre = self.tail, self.head

    def get(self, key: int) -> int:
        if key not in self.cachedMap:
            return -1
        node = self.cachedMap[key]
        self.moveNodeToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cachedMap:  # 元素没在cache中，才需要新建节点，并将节点插入到链表头部
            newNode = Node(key, value)
            self.cachedMap[key] = newNode
            self.addNodeToHead(newNode)
            size = len(self.cachedMap)
            if size > self.capacity:
                del self.cachedMap[self.tail.pre.key]
                self.removeNode(self.tail.pre)
        else:  # 元素在cache中，直接修改对应节点的value，然后将节点移到头部即可
            tmpNode = self.cachedMap[key]
            tmpNode.value = value
            self.moveNodeToHead(tmpNode)

    def moveNodeToHead(self, node: Node) -> None:  # 先将元素删除，然后再添加到头部(好处可以不用遍历整个链表)
        self.removeNode(node)
        self.addNodeToHead(node)

    def removeNode(self, node: Node) -> None:
        node.pre.next = node.next
        node.next.pre = node.pre

    def addNodeToHead(self, node: Node) -> None:
        node.pre = self.head
        node.next = self.head.next
        self.head.next.pre = node
        self.head.next = node


class LRUCacheByOrderedDict(OrderedDict):  # OrderedDict 类似于java中的LinkedHashMap

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key, last=False)
        return self[key]

    def put(self, key: int, value: int) -> None:
        self[key] = value
        self.move_to_end(key, last=False)
        if self.__len__() > self.capacity:
            self.popitem(last=True)


if __name__ == "__main__":
    lru = LRUCache(2)
    # ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
    # [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
    lru.put(1, 1)
    lru.put(2, 2)
    print(lru.get(1))
    lru.put(3, 3)
    print(lru.get(2))
    lru.put(4, 4)
    print(lru.get(1))
    print(lru.get(3))
    print(lru.get(4))
